<!DOCTYPE html>



  


<html class="theme-next gemini use-motion" lang="zh-Hans">
<head><meta name="generator" content="Hexo 3.8.0">
  <meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
<meta name="theme-color" content="#222">









<meta http-equiv="Cache-Control" content="no-transform">
<meta http-equiv="Cache-Control" content="no-siteapp">
















  
  
  <link href="/s_l/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css">







<link href="/s_l/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css">

<link href="/s_l/css/main.css?v=5.1.4" rel="stylesheet" type="text/css">


  <link rel="apple-touch-icon" sizes="180x180" href="/s_l/images/apple-touch-icon-next.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="32x32" href="/s_l/images/favicon-32x32-next.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="16x16" href="/s_l/images/favicon-16x16-next.png?v=5.1.4">


  <link rel="mask-icon" href="/s_l/images/logo.svg?v=5.1.4" color="#222">





  <meta name="keywords" content="java集合,">










<meta name="description" content="在Map集合实现类中，最重要的就是HashMap，本文将主要深入HashMap的底层代码，仔细分析一下HashMap">
<meta name="keywords" content="java集合">
<meta property="og:type" content="article">
<meta property="og:title" content="深入HashMap">
<meta property="og:url" content="http://yoursite.com/2019/05/09/深入HashMap/index.html">
<meta property="og:site_name" content="S.L">
<meta property="og:description" content="在Map集合实现类中，最重要的就是HashMap，本文将主要深入HashMap的底层代码，仔细分析一下HashMap">
<meta property="og:locale" content="zh-Hans">
<meta property="og:updated_time" content="2019-05-09T10:51:04.583Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="深入HashMap">
<meta name="twitter:description" content="在Map集合实现类中，最重要的就是HashMap，本文将主要深入HashMap的底层代码，仔细分析一下HashMap">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/s_l/',
    scheme: 'Gemini',
    version: '5.1.4',
    sidebar: {"position":"left","display":"post","offset":12,"b2t":false,"scrollpercent":false,"onmobile":false},
    fancybox: true,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    duoshuo: {
      userId: '0',
      author: '博主'
    },
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="http://yoursite.com/2019/05/09/深入HashMap/">





  <title>深入HashMap | S.L</title>
  








</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-Hans">

  
  
    
  

  <div class="container sidebar-position-left page-post-detail">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/s_l/" class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">S.L</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <p class="site-subtitle">记录学习过程中的点滴</p>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/s_l/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br>
            
            首页
          </a>
        </li>
      
        
        <li class="menu-item menu-item-about">
          <a href="/s_l/about/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-user"></i> <br>
            
            关于
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/s_l/tags/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-tags"></i> <br>
            
            标签
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/s_l/categories/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-th"></i> <br>
            
            分类
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/s_l/archives/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br>
            
            归档
          </a>
        </li>
      

      
    </ul>
  

  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://yoursite.com/s_l/2019/05/09/深入HashMap/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="苏立鹏">
      <meta itemprop="description" content>
      <meta itemprop="image" content="/s_l/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="S.L">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">深入HashMap</h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2019-05-09T14:52:39+08:00">
                2019-05-09
              </time>
            

            

            
          </span>

          

          
            
          

          
          

          

          
            <div class="post-wordcount">
              
                
                <span class="post-meta-item-icon">
                  <i class="fa fa-file-word-o"></i>
                </span>
                
                  <span class="post-meta-item-text">字数统计&#58;</span>
                
                <span title="字数统计">
                  2.5k 字
                </span>
              

              
                <span class="post-meta-divider">|</span>
              

              
                <span class="post-meta-item-icon">
                  <i class="fa fa-clock-o"></i>
                </span>
                
                  <span class="post-meta-item-text">阅读时长 &asymp;</span>
                
                <span title="阅读时长">
                  10 分钟
                </span>
              
            </div>
          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        <blockquote>
<p>在Map集合实现类中，最重要的就是HashMap，本文将主要深入HashMap的底层代码，仔细分析一下HashMap</p>
</blockquote>
<a id="more"></a>
<h3 id="HashMap定义"><a href="#HashMap定义" class="headerlink" title="HashMap定义"></a>HashMap定义</h3><p>HashMap是 Map 接口使用频率最高的实现类，<strong>允许使用null键和null值</strong>，与HashSet一样，不保证映射的顺序。所有的key构成的集合是Set:无序的、不可重复的。所以，key所在的类要重写：equals()和hashCode()<br>所有的value构成的集合是Collection:无序的、可以重复的。所以，value所在的类要重写：equals()<br>一个key-value构成一个entry<br>所有的entry构成的集合是Set:无序的、不可重复的<br>HashMap 判断两个 key 相等的标准是：两个 key 通过 equals() 方法返回 true，hashCode 值也相等。<br>HashMap 判断两个 value相等的标准是：两个 value 通过 equals() 方法返回 true。</p>
<h3 id="HashMap底层存储结构"><a href="#HashMap底层存储结构" class="headerlink" title="HashMap底层存储结构"></a>HashMap底层存储结构</h3><p>HashMap的底层存储分为JDK1.7和JDK1.8两个不同的版本，JDK1.7的版本是数组加链表，JDK1.8以后是数组加链表和红黑树。</p>
<h3 id="HashMap中的重要常量值"><a href="#HashMap中的重要常量值" class="headerlink" title="HashMap中的重要常量值"></a>HashMap中的重要常量值</h3><table>
<thead>
<tr>
<th>常量名</th>
<th>作用</th>
</tr>
</thead>
<tbody>
<tr>
<td>DEFAULT_INITIAL_CAPACITY</td>
<td>HashMap的默认容量   ，默认16</td>
</tr>
<tr>
<td>MAXIMUM_CAPACITY</td>
<td>HashMap的最大支持容量，2^30</td>
</tr>
<tr>
<td>DEFAULT_LOAD_FACTOR</td>
<td>HashMap的默认加载因子</td>
</tr>
<tr>
<td>TREEIFY_THRESHOLD</td>
<td>Bucket中链表长度大于该默认值，转化为红黑树</td>
</tr>
<tr>
<td>UNTREEIFY_THRESHOLD</td>
<td>Bucket中红黑树存储的Node小于该默认值，转化为链表</td>
</tr>
<tr>
<td>MIN_TREEIFY_CAPACITY</td>
<td>桶中的Node被树化时最小的hash表容量</td>
</tr>
<tr>
<td>table</td>
<td>存储元素的数组，总是2的n次幂</td>
</tr>
<tr>
<td>entrySet</td>
<td>存储具体元素的集</td>
</tr>
<tr>
<td>size</td>
<td>HashMap中存储的键值对的数量</td>
</tr>
<tr>
<td>modCount</td>
<td>HashMap扩容和结构改变的次数</td>
</tr>
<tr>
<td>threshold</td>
<td>扩容的临界值，=容量*/填充因子</td>
</tr>
<tr>
<td>loadFactor</td>
<td>填充因子</td>
</tr>
</tbody>
</table>
<h3 id="HashMap的put-K-V"><a href="#HashMap的put-K-V" class="headerlink" title="HashMap的put(K,V)"></a>HashMap的put(K,V)</h3><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment">   * 源码中的put调用了 putVal(hash(key), key, value, false, true);</span></span><br><span class="line"><span class="comment">   * 主要目的是将传入的key值先做一步Hash运算，将key计算过后的hash和key值还有value传入到方法中</span></span><br><span class="line"><span class="comment">   */</span></span><br><span class="line">  <span class="function"><span class="keyword">public</span> V <span class="title">put</span><span class="params">(K key, V value)</span> </span>&#123;</span><br><span class="line">      <span class="keyword">return</span> putVal(hash(key), key, value, <span class="keyword">false</span>, <span class="keyword">true</span>);</span><br><span class="line">  &#125;</span><br></pre></td></tr></table></figure>
<p>接下来源码中的putVal很长  不过我们可以一点一点的分析其中的目的和想法</p>
<figure class="highlight javascript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment">    * Implements Map.put and related methods.</span></span><br><span class="line"><span class="comment">    *</span></span><br><span class="line"><span class="comment">    * @param hash hash for key</span></span><br><span class="line"><span class="comment">    * @param key the key</span></span><br><span class="line"><span class="comment">    * @param value the value to put</span></span><br><span class="line"><span class="comment">    * @param onlyIfAbsent if true, don't change existing value</span></span><br><span class="line"><span class="comment">    * @param evict if false, the table is in creation mode.</span></span><br><span class="line"><span class="comment">    * @return previous value, or null if none</span></span><br><span class="line"><span class="comment">    */</span></span><br><span class="line">   final V putVal(int hash, K key, V value, boolean onlyIfAbsent,</span><br><span class="line">                  boolean evict) &#123;</span><br><span class="line">       Node&lt;K,V&gt;[] tab; Node&lt;K,V&gt; p; int n, i;</span><br><span class="line">       <span class="keyword">if</span> ((tab = table) == <span class="literal">null</span> || (n = tab.length) == <span class="number">0</span>)</span><br><span class="line">           n = (tab = resize()).length;</span><br><span class="line">       <span class="keyword">if</span> ((p = tab[i = (n - <span class="number">1</span>) &amp; hash]) == <span class="literal">null</span>)</span><br><span class="line">           tab[i] = newNode(hash, key, value, <span class="literal">null</span>);</span><br><span class="line">       <span class="keyword">else</span> &#123;</span><br><span class="line">           Node&lt;K,V&gt; e; K k;</span><br><span class="line">           <span class="keyword">if</span> (p.hash == hash &amp;&amp;</span><br><span class="line">               ((k = p.key) == key || (key != <span class="literal">null</span> &amp;&amp; key.equals(k))))</span><br><span class="line">               e = p;</span><br><span class="line">           <span class="keyword">else</span> <span class="keyword">if</span> (p <span class="keyword">instanceof</span> TreeNode)</span><br><span class="line">               e = ((TreeNode&lt;K,V&gt;)p).putTreeVal(<span class="keyword">this</span>, tab, hash, key, value);</span><br><span class="line">           <span class="keyword">else</span> &#123;</span><br><span class="line">               <span class="keyword">for</span> (int binCount = <span class="number">0</span>; ; ++binCount) &#123;</span><br><span class="line">                   <span class="keyword">if</span> ((e = p.next) == <span class="literal">null</span>) &#123;</span><br><span class="line">                       p.next = newNode(hash, key, value, <span class="literal">null</span>);</span><br><span class="line">                       <span class="keyword">if</span> (binCount &gt;= TREEIFY_THRESHOLD - <span class="number">1</span>) <span class="comment">// -1 for 1st</span></span><br><span class="line">                           treeifyBin(tab, hash);</span><br><span class="line">                       <span class="keyword">break</span>;</span><br><span class="line">                   &#125;</span><br><span class="line">                   <span class="keyword">if</span> (e.hash == hash &amp;&amp;</span><br><span class="line">                       ((k = e.key) == key || (key != <span class="literal">null</span> &amp;&amp; key.equals(k))))</span><br><span class="line">                       <span class="keyword">break</span>;</span><br><span class="line">                   p = e;</span><br><span class="line">               &#125;</span><br><span class="line">           &#125;</span><br><span class="line">           <span class="keyword">if</span> (e != <span class="literal">null</span>) &#123; <span class="comment">// existing mapping for key</span></span><br><span class="line">               V oldValue = e.value;</span><br><span class="line">               <span class="keyword">if</span> (!onlyIfAbsent || oldValue == <span class="literal">null</span>)</span><br><span class="line">                   e.value = value;</span><br><span class="line">               afterNodeAccess(e);</span><br><span class="line">               <span class="keyword">return</span> oldValue;</span><br><span class="line">           &#125;</span><br><span class="line">       &#125;</span><br><span class="line">       ++modCount;</span><br><span class="line">       <span class="keyword">if</span> (++size &gt; threshold)</span><br><span class="line">           resize();</span><br><span class="line">       afterNodeInsertion(evict);</span><br><span class="line">       <span class="keyword">return</span> <span class="literal">null</span>;</span><br><span class="line">   &#125;</span><br></pre></td></tr></table></figure>
<p>一开始源码中在检测table是否为null，这个table就是常量值中的table，是hashmap底层中的数组</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//如果table为null调用扩容方法，扩容方法我们将在下一节</span></span><br><span class="line"><span class="comment">//扩容和树形化中说明</span></span><br><span class="line"> <span class="keyword">if</span> ((tab = table) == <span class="keyword">null</span> || (n = tab.length) == <span class="number">0</span>)</span><br><span class="line">            n = (tab = resize()).length;</span><br></pre></td></tr></table></figure>
<p>如果table不为null，扩容完毕以后，put方法会继续检查索引位置上是否有元素<code>[i = (n - 1) &amp; hash]</code> 这个算的是元素应该存放在数组中的索引位置，n是table的长度-1得到的</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//这段代码是说，如果tab[i]的位置上没有元素，则直接存入</span></span><br><span class="line"><span class="comment">//如果有元素就进入下一个更复杂的对比中</span></span><br><span class="line"> <span class="keyword">if</span> ((p = tab[i = (n - <span class="number">1</span>) &amp; hash]) == <span class="keyword">null</span>)</span><br><span class="line">            tab[i] = newNode(hash, key, value, <span class="keyword">null</span>);</span><br></pre></td></tr></table></figure>
<p>如果要存入的元素在tab[i]上有了，那么就分为三种情况<br>1.要存入的元素和数组位置上的元素hash值相等,并且使用equals()比较也相等<br><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//源码中不是这样写的，这段代码是分开的，</span></span><br><span class="line"><span class="comment">//但是他们是相关联的，代码的结果就是如果</span></span><br><span class="line"><span class="comment">//hash值相等,并且使用equals()比较也相等,就使用新的值替换旧的值</span></span><br><span class="line">  <span class="keyword">if</span> (p.hash == hash &amp;&amp;</span><br><span class="line">                ((k = p.key) == key || (key != <span class="keyword">null</span> &amp;&amp; key.equals(k))))</span><br><span class="line">                e = p;</span><br><span class="line">   <span class="keyword">if</span> (e != <span class="keyword">null</span>) &#123; <span class="comment">// existing mapping for key</span></span><br><span class="line">                V oldValue = e.value;</span><br><span class="line">                <span class="keyword">if</span> (!onlyIfAbsent || oldValue == <span class="keyword">null</span>)</span><br><span class="line">                    e.value = value;</span><br><span class="line">                afterNodeAccess(e);</span><br><span class="line">                <span class="keyword">return</span> oldValue;</span><br><span class="line">            &#125;</span><br></pre></td></tr></table></figure></p>
<p>2.要存入的元素和数组位置上的元素hash值不相等，就要循环遍历数组位置上的链表<br>下面代码的执行是将当前要存入的key-value和链表上所有的键值对比较完毕，如果没有相同的值，则插入<br><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">for</span> (<span class="keyword">int</span> binCount = <span class="number">0</span>; ; ++binCount) &#123;</span><br><span class="line">                   <span class="keyword">if</span> ((e = p.next) == <span class="keyword">null</span>) &#123;</span><br><span class="line">                       p.next = newNode(hash, key, value, <span class="keyword">null</span>);</span><br><span class="line">                       <span class="keyword">if</span> (binCount &gt;= TREEIFY_THRESHOLD - <span class="number">1</span>) <span class="comment">// -1 for 1st</span></span><br><span class="line">                           treeifyBin(tab, hash);</span><br><span class="line">                       <span class="keyword">break</span>;</span><br><span class="line">                   &#125;</span><br><span class="line">                   <span class="keyword">if</span> (e.hash == hash &amp;&amp;</span><br><span class="line">                       ((k = e.key) == key || (key != <span class="keyword">null</span> &amp;&amp; key.equals(k))))</span><br><span class="line">                       <span class="keyword">break</span>;</span><br><span class="line">                   p = e;</span><br><span class="line">               &#125;</span><br></pre></td></tr></table></figure></p>
<h3 id="HashMap的扩容和树形化"><a href="#HashMap的扩容和树形化" class="headerlink" title="HashMap的扩容和树形化"></a>HashMap的扩容和树形化</h3><p>当HashMap中的元素越来越多的时候，hash冲突的几率也就越来越高，因为数组的长度是固定的。所以为了提高查询的效率，就要对HashMap的数组进行扩容，而在HashMap数组扩容之后，最消耗性能的点就出现了：<strong>原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize</strong>。<br>数组扩容极为消耗性能，问题在于其中的元素需要重新计算hash码，以确认其在新数组中的位置。</p>
<h4 id="什么时候扩容？"><a href="#什么时候扩容？" class="headerlink" title="什么时候扩容？"></a>什么时候扩容？</h4><p>当HashMap中的元素个数超过数组大小(数组总大小length,不是数组中个数size)*loadFactor时，就会进行数组扩容，loadFactor的默认值(DEFAULT_LOAD_FACTOR)为0.75，这是一个折中的取值。也就是说，默认情况下，数组大小(DEFAULT_INITIAL_CAPACITY)为16，那么当HashMap中元素个数超过16*0.75=12（这个值就是代码中的threshold值，也叫做临界值）的时候，就把数组的大小扩展为 2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。</p>
<h4 id="树形化的源来"><a href="#树形化的源来" class="headerlink" title="树形化的源来"></a>树形化的源来</h4><p>当实例化一个HashMap时，会初始化initialCapacity和loadFactor，在put第一对映射关系时，系统会创建一个长度为initialCapacity的Node数组，这个长度在哈希表中被称为容量(Capacity)，在这个数组中可以存放元素的位置我们称之为“桶”(bucket)，每个bucket都有自己的索引，系统可以根据索引快速的查找bucket中的元素。</p>
<p>每个bucket中存储一个元素，即一个Node对象，但每一个Node对象可以带一个引用变量next，用于指向下一个元素，因此，在一个桶中，就有可能生成一个Node链。也可能是一个一个TreeNode对象，每一个TreeNode对象可以有两个叶子结点left和right，因此，在一个桶中，就有可能生成一个TreeNode树。而新添加的元素作为链表的last，或树的叶子结点。</p>
<h4 id="为什么树形化？"><a href="#为什么树形化？" class="headerlink" title="为什么树形化？"></a>为什么树形化？</h4><p>当存入一个元素到map中的数组时，发现数组索引位置上已经存在了一个Node节点，那么就要和这个Node节点以及其所有子节点进行一个一个对比hash和equals()是否相等，如果这个链表很长呢？遍历一遍会非常消耗时间，而使用树，则可以将时间缩短很多，原因在于树形结构上，树形结构的二叉性可以使得每一次遍历都可以少遍历一半的元素，非常高效</p>
<h4 id="HashMap什么时候树形化？"><a href="#HashMap什么时候树形化？" class="headerlink" title="HashMap什么时候树形化？"></a>HashMap什么时候树形化？</h4><p>当HashMap中的元素个数超过数组大小(数组总大小length,不是数组中个数size)*loadFactor时，就会进行数组扩容，loadFactor的默认值(DEFAULT_LOAD_FACTOR)为0.75，这是一个折中的取值。也就是说，默认情况下，数组大小(DEFAULT_INITIAL_CAPACITY)为16，那么当HashMap中元素个数超过16*0.75=12（这个值就是代码中的threshold值，也叫做临界值）的时候，就把数组的大小扩展为 2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。</p>
<p>当HashMap中的其中一个链的对象个数如果达到了8个，此时如果capacity没有达到64，那么HashMap会先扩容解决，如果已经达到了64，那么这个链会变成树，结点类型由Node变成TreeNode类型。当然，如果当映射关系被移除后，下次resize方法时判断树的结点个数低于6个，也会把树再转为链表。</p>
<h3 id="HashMap负载因子值的大小，对HashMap有什么影响"><a href="#HashMap负载因子值的大小，对HashMap有什么影响" class="headerlink" title="HashMap负载因子值的大小，对HashMap有什么影响"></a>HashMap负载因子值的大小，对HashMap有什么影响</h3><p>负载因子的大小决定了HashMap的数据密度。<br>负载因子越大密度越大，发生碰撞的几率越高，数组中的链表越容易长,造成查询或插入时的比较次数增多，性能会下降。<br>负载因子越小，就越容易触发扩容，数据密度也越小，意味着发生碰撞的几率越小，数组中的链表也就越短，查询和插入时比较的次数也越小，性能会更高。但是会浪费一定的内容空间。而且经常扩容也会影响性能，建议初始化预设大一点的空间。<br>按照其他语言的参考及研究经验，会考虑将负载因子设置为0.7~0.75，此时平均检索长度接近于常数</p>
<p>182 0839</p>
<p>  67 7833</p>

      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      
        <div class="post-tags">
          
            <a href="/s_l/tags/java集合/" rel="tag"># java集合</a>
          
        </div>
      

      
      
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/s_l/2019/05/09/集合框架/" rel="next" title="集合框架">
                <i class="fa fa-chevron-left"></i> 集合框架
              </a>
            
          </div>

          <span class="post-nav-divider"></span>

          <div class="post-nav-prev post-nav-item">
            
          </div>
        </div>
      

      
      
    </footer>
  </div>
  
  
  
  </article>



    <div class="post-spread">
      
    </div>
  </div>


          </div>
          


          

  



        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap">
            文章目录
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview-wrap">
            站点概览
          </li>
        </ul>
      

      <section class="site-overview-wrap sidebar-panel">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <p class="site-author-name" itemprop="name">苏立鹏</p>
              <p class="site-description motion-element" itemprop="description"></p>
          </div>

          <nav class="site-state motion-element">

            
              <div class="site-state-item site-state-posts">
              
                <a href="/s_l/archives/">
              
                  <span class="site-state-item-count">8</span>
                  <span class="site-state-item-name">日志</span>
                </a>
              </div>
            

            

            
              
              
              <div class="site-state-item site-state-tags">
                
                  <span class="site-state-item-count">3</span>
                  <span class="site-state-item-name">标签</span>
                
              </div>
            

          </nav>

          

          
            <div class="links-of-author motion-element">
                
                  <span class="links-of-author-item">
                    <a href="https://gitee.com/www.86740.com/projects" target="_blank" title="GitHub">
                      
                        <i class="fa fa-fw fa-github"></i>GitHub</a>
                  </span>
                
            </div>
          

          
          

          
          

          

        </div>
      </section>

      
      <!--noindex-->
        <section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc">

            
              
            

            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-3"><a class="nav-link" href="#HashMap定义"><span class="nav-number">1.</span> <span class="nav-text">HashMap定义</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#HashMap底层存储结构"><span class="nav-number">2.</span> <span class="nav-text">HashMap底层存储结构</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#HashMap中的重要常量值"><span class="nav-number">3.</span> <span class="nav-text">HashMap中的重要常量值</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#HashMap的put-K-V"><span class="nav-number">4.</span> <span class="nav-text">HashMap的put(K,V)</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#HashMap的扩容和树形化"><span class="nav-number">5.</span> <span class="nav-text">HashMap的扩容和树形化</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#什么时候扩容？"><span class="nav-number">5.1.</span> <span class="nav-text">什么时候扩容？</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#树形化的源来"><span class="nav-number">5.2.</span> <span class="nav-text">树形化的源来</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#为什么树形化？"><span class="nav-number">5.3.</span> <span class="nav-text">为什么树形化？</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#HashMap什么时候树形化？"><span class="nav-number">5.4.</span> <span class="nav-text">HashMap什么时候树形化？</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#HashMap负载因子值的大小，对HashMap有什么影响"><span class="nav-number">6.</span> <span class="nav-text">HashMap负载因子值的大小，对HashMap有什么影响</span></a></li></ol></div>
            

          </div>
        </section>
      <!--/noindex-->
      

      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; <span itemprop="copyrightYear">2019</span>
  <span class="with-love">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">苏立鹏</span>

  
</div>


  <div class="powered-by">由 <a class="theme-link" target="_blank" href="https://hexo.io">Hexo</a> 强力驱动</div>



  <span class="post-meta-divider">|</span>



  <div class="theme-info">主题 &mdash; <a class="theme-link" target="_blank" href="https://github.com/iissnan/hexo-theme-next">NexT.Gemini</a> v5.1.4</div>




        







        
      </div>
    </footer>

    
      <div class="back-to-top">
        <i class="fa fa-arrow-up"></i>
        
      </div>
    

    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  












  
  
    <script type="text/javascript" src="/s_l/lib/jquery/index.js?v=2.1.3"></script>
  

  
  
    <script type="text/javascript" src="/s_l/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>
  

  
  
    <script type="text/javascript" src="/s_l/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>
  

  
  
    <script type="text/javascript" src="/s_l/lib/velocity/velocity.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/s_l/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/s_l/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>
  


  


  <script type="text/javascript" src="/s_l/js/src/utils.js?v=5.1.4"></script>

  <script type="text/javascript" src="/s_l/js/src/motion.js?v=5.1.4"></script>



  
  


  <script type="text/javascript" src="/s_l/js/src/affix.js?v=5.1.4"></script>

  <script type="text/javascript" src="/s_l/js/src/schemes/pisces.js?v=5.1.4"></script>



  
  <script type="text/javascript" src="/s_l/js/src/scrollspy.js?v=5.1.4"></script>
<script type="text/javascript" src="/s_l/js/src/post-details.js?v=5.1.4"></script>



  


  <script type="text/javascript" src="/s_l/js/src/bootstrap.js?v=5.1.4"></script>



  


  




	





  





  












  





  

  

  

  
  

  

  

  

</body>
</html>
